import java.util.*;

/**
 * 128. Longest Consecutive Sequence 最长连续序列
 * https://leetcode.com/problems/longest-consecutive-sequence/
 */
class LongestConsecutiveSequence {
    /**
     * 方法：使用HashSet存储所有数字，然后遍历每个数字，如果当前数字是序列的起点（即不存在前一个数字），则向后查找连续序列
     * Args: int[] nums - 输入的整数数组
     * Returns: int - 最长连续序列的长度
     * Time: O(n) - 每个数字最多被访问两次
     * Space: O(n) - 使用HashSet存储所有数字
     */
    public int longestConsecutive(int[] nums) {
        int ans = 0;
        Set<Integer> st = new HashSet<>();
        for(int num : nums){
            st.add(num);
        }
        for(int x : st){
            if(st.contains(x-1)){
                continue;
            }
            int y = x + 1;
            while(st.contains(y)){
                y++;
            }
            ans = Math.max(ans, y-x);
        }
        return ans;
    }
}